/*
    这是我马上就会用上的，在spi flash里存储数据的搜索方式
    它基于已经写过的数据，不可能出现，2字节 4字节 或者更多的2^n 不可能出现连续 FF
    1、对于字符串，这个问题不用担心，因为它永远不会出现；
    2、对于2字节、4字节、8字节，在针对到 uint16_t uint32_t uint64_t 或者 float时，是要小心的；
    3、所以，最好的办法是，只要能避免，尽量保证自己存储的数据是 带符号位，然后不存入 -1 或者 FFFFFFF
       否则，处理起来会相当麻烦

    1、在一个 4字节长度（比如为uint32_t）数组 uint32_t A[N],前m个数据非0xFFFFFFF,m+1到n-1 为全0xFFFFFFFF,请设计一个高效算法，查找m的位置。
    显然，这个题目是对上述sector的抽象，而这个问题，显然是可以使用二分查找法。

    进一步,我需要验证这个算法是否确实有效
    对于char A[size]，A的前半部分已经存入无序非0元素，A的后半部分全部为0.

    请采用快速的查找方法，找到无序非0元素的长度。

    这个方法，之所以可以用二分查找，是因为——
    如果我们把 char A[size]，看成是 short B[size/2];
    那么，无须非0元素出现的位置，一定就是在一个 0xXX00的地方。
    而这个元素的类型，在B中是唯一的，而且，有且只有一个。
    而它的左边全部是 0xXXXX,右边全部是 0x0000。由于我们并不关心，0xXXXX的大小问题，而0x0000显然也全部是0。
    对于任何一个B，它的左侧、右侧，永远可以区分 全0xXXXX 和 0x0000
*/

/*  
    在PC上模拟 spi flash空间 256B 到 任何 256B 的整数倍，乃至到 1MB ——但是，我可能无法实现这么大的数据？ 
    试试

    在算法中，统计使用的次数，并在最后输出，是否满足 小于等于 log2(n)
    log2(n) 是 C语言标准库 math 里的一个函数
    double log2(double n)
*/
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <math.h>

#define FLASH_UNIT_COUNT (1024 * 1024)
#define FLASH_UNIT_SIZE (sizeof(uint32_t))
#define FLASH_CAPACITY  (FLASH_UNIT_COUNT * FLASH_UNIT_SIZE)
uint32_t *p_flash;
size_t binary_count = 0;

void alloc_spi_flash(void)
{
    p_flash = (uint32_t *)malloc(FLASH_CAPACITY);
    if(NULL == p_flash)
        printf("cannot allocate %d\n",FLASH_CAPACITY);
}

void set_spi_flash(uint32_t n)
{
    #define X 0x5AA555AA

    uint32_t i;
    uint32_t *p = p_flash;

    if(n > FLASH_UNIT_COUNT)
    {
        printf("set flash N is exceed flash size!\n");
        return;
    }

    for(i = 0;i < n;i++)
        *(p++) = X;

    if(FLASH_UNIT_COUNT == n)
        return;

    for(;i < FLASH_UNIT_COUNT;i++)
        *(p++) = 0xffffffff;

    // printf("flash has unit:%d\n",FLASH_UNIT_COUNT);

    // printf("%x \t %x \t %x \t %x \t"  ,p_flash[0] ,p_flash[1] ,p_flash[2] ,p_flash[3]);
    // printf("%x \t %x \t %x \t %x \t\n",p_flash[4] ,p_flash[5] ,p_flash[6] ,p_flash[7]);
    // printf("%x \t %x \t %x \t %x \t"  ,p_flash[8] ,p_flash[9] ,p_flash[10],p_flash[11]);
    // printf("%x \t %x \t %x \t %x \t\n",p_flash[12],p_flash[13],p_flash[14],p_flash[15]);    
}

double cal_upper(unsigned long long n)
{
    double fn;
    fn = (double)n;
    return log2(fn);
}

// --------------------------------------------------
typedef enum 
{
    UNIT_MATCH,
    UNIT_IN_LEFT,
    UNIT_IN_RIGHT,
    UNIT_ERROR,
}st_unit_type;

static st_unit_type detect_unit_type(uint32_t *data)
{
    uint32_t data0,data1;
    data0 = *data;
    data1 = *(data + 1);

    if(0xFFFFFFFF == data0)
    {
        if(0xFFFFFFFF == data1)
            return UNIT_IN_LEFT;
        else
            return UNIT_ERROR;
    }
    else
    {
        if(0xFFFFFFFF == data1)
            return UNIT_MATCH;
        else
            return UNIT_IN_RIGHT;        
    }
}

uint32_t binary_search_last_place(void)
{
    uint32_t len;
    uint32_t start,end,mid;
    st_unit_type unit_type;

    binary_count = 0;

    len = FLASH_UNIT_COUNT / 2;

    start = 0;
    end = len - 1;

    while(1)
    {
        mid = (start + end) / 2;
        binary_count++;
        if(1 == len)
        {
            if(UNIT_MATCH == detect_unit_type(p_flash + mid) )
                return mid;
            else 
                return 0;      // 这不叫失败.....这叫结束
        }
        else if(2 == len)
        {
            if(UNIT_MATCH == detect_unit_type(p_flash + start) )
                return start;
            else if(UNIT_MATCH == detect_unit_type(p_flash + end) )
                return end;
            else
                return 0;
        }
        else
        {
            unit_type = detect_unit_type(p_flash + mid);
            //printf("unit type:%d\n",unit_type);
            switch(unit_type)
            {
                case UNIT_MATCH:
                    return mid;
                break;

                case UNIT_IN_LEFT:
                    end = mid - 1;
                break;                

                case UNIT_IN_RIGHT:
                    start = mid + 1;
                break;
                
                case UNIT_ERROR:
                    printf("There is unit error!!!\n");
                    return -1;
                break; 

                default:        // 不可能到这个位置
                    return;         // 所以退出为好，避免死循环     
                // break;            
            }
        }
        
        len = end - start + 1;
    }
}


// -------------------------------------------------
void test_binary_search_4_flash_sector(void)
{
    uint32_t found_pos;
    uint32_t pos;

    alloc_spi_flash();

    for(pos = 0;pos < FLASH_UNIT_COUNT;pos++)
    {
        set_spi_flash(pos);

        found_pos = binary_search_last_place();
        if(-1 == found_pos)
            printf("search failed!\n");

        // 检查 & 打印是否成功
        // 次数统计 & 判断是否小于 log2(n)
        if(binary_count > log2(FLASH_UNIT_COUNT))
        {
            printf("search times failed!\nwhen pos at %x\n",pos);
            return;
        }

        if(0xffff == (pos & 0xffff))
            printf("finish ~%x pos test.\n",pos);
    }

    if(NULL != p_flash)
    {
        free(p_flash);
        p_flash = NULL;
    }
}


// end of file ----------------------------------------------------------------
